package binarysearchtree;

/**
 * @Author 比特就业课
 * @Date 2022-11-14
 */
public class BinarySearchTreeReview {
    public static void main(String[] args) {
        BinarySearchTreeReview binarySearchTree = new BinarySearchTreeReview();
        int[] arr = {1, 3, 5, 6, 9, 8, 7, 10};
        for (int i = 0; i < arr.length; ++i) {
            binarySearchTree.insert(arr[i]);
        }
        System.out.println(binarySearchTree.inorder(binarySearchTree.root));
         System.out.println(binarySearchTree.search(1));
        //测试删除结点
        binarySearchTree.remove(7);
        System.out.println(binarySearchTree.inorder(binarySearchTree.root));
    }

    // 定义节点类
    private static class TreeNode {
        int value;
        TreeNode left;
        TreeNode right;

        public TreeNode(int value) {
            this.value = value;
        }
    }

    // 定义一个根节点的引用
    public TreeNode root;

    /**
     * 查找指定的值是否存在
     *
     * @param value
     * @return
     */
    public boolean search(int value) {
        //校验树的有效性
        if (root == null) {
            return false;
        }
        //进行寻找操作
        TreeNode cur=root;
        while(cur!=null){
            //根据二叉搜索树的排序规则进行查找
            if(cur.value==value){
                return true;
            }
            if(cur.value<value){
                cur=cur.right;
            }
            if(cur.value>value){
                cur=cur.left;
            }
        }
        //直到cur==null则说明并没有找到
        return false;

    }

    /**
     * 插入一个元素
     *
     * @param value 要插入的值
     * @return
     */
    public boolean insert(int value) {
        //创建新结点
        TreeNode treeNode = new TreeNode(value);
        //校验根结点
        if(root==null){
            root=treeNode;
            return true;
        }
        //需要父子双结点进行查找，子节点负责向下遍历，父节点负责树的对接
        TreeNode parent=null;
        TreeNode cur=root;
        //查找时就是按照查找逻辑
        while(cur!=null){
            //处理相同节点情况
            if(cur.value==value){
                return false;
            }
            //将当前结点进行保存
            parent=cur;
            if(cur.value<value){
                //放在右边
                cur=cur.right;
            }
           else{
                cur=cur.left;
            }
        }
        //找到之后加入即可
        if(parent.value>value){
            parent.left=treeNode;
        }
        else {
            parent.right=treeNode;
        }
        return true;
    }

    /**
     * 删除指定的元素
     *
     * @param value 要删除的元素
     * @return
     */
    public boolean remove(int value) {
        //检验树的有效性
        if(root==null){
            return false;
        }
        //建立父子双结点进行遍历
        TreeNode cur=root;
        TreeNode parent=null;
        //寻找结点
        while(cur!=null){
            if(cur.value==value){
                removeNode(parent,cur);
                return true;
            }
            //将当前结点进行保存
            parent=cur;
            //向左向右进行遍历
            if(cur.value<value){
                cur=cur.right;
            }
            else{
                cur=cur.left;
            }
        }
        return false;
    }

    /**
     * 分类讨论要删除节点的不同情况
     *
     * @param parent 父节点
     * @param cur    子节点
     */
    private void removeNode(TreeNode parent, TreeNode cur) {
        //处理cur没有左子节点的情况
        if(cur.left==null){
            //如果是根结点
            if(cur==root){
                root=cur.right;
            }
            //如果是父节点的左子节点
            if(parent.left==cur)
                parent.left=cur.right;
            //如果是父节点的右子节点
            if(parent.right==cur)
                parent.right=cur.right;
        }
        //处理cur没有右子结点的情况
        else if (cur.right==null) {
            //处理cur为根的情况
            if(cur==root){
                root=cur.left;
            }
            //处理cur为父节点的左子节点
            if(parent.left==cur){
                parent.left=cur.left;
            }
            //处理cur为父节点的右子节点
            if(parent.right==cur)
            {
                parent.right=cur.left;
            }

        }
        //对cur既有左子节点又有右子结点的情况进行处理
        else{
            //用左子节点的最大值替换或者右子结点的最小值替换
            //notes：此处处理逻辑为替换，之前两种情况处理逻辑为删除，略有不同
          TreeNode curParent=cur;
            //找左子树的右子结点(或者右子树的最左子节点也可以)
            TreeNode target=cur.left;
            while(target.right!=null){
                curParent=target;
                target=target.right;
            }
            //替换
            cur.value=target.value;
            //删除左子节点的最右子结点
            if(curParent.left==target){
                curParent.left=null;
            }
            else {
                curParent.right=null;
            }


        }

    }

    /**
     * 中序遍历
     *
     * @param node
     * @return
     */
    public String inorder(TreeNode node) {
        //建立StringBuilder
        StringBuilder sb = new StringBuilder();
        //检查根的有效性
        if(node==null){
            return sb.toString();
        }
        //将左子树加入
        String string = inorder(node.left);
        sb.append(string);
        //将中间结点加入
        sb.append(node.value+" ");
        //将右子树加入
        String inorder = inorder(node.right);
        sb.append(inorder);
        return sb.toString();
    }
}
